#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
const int N = 500050;
//vector<TreeNode*> e[N];
long long  d[N];
int f[N][31];
class Solution {
public:
    void dfs(TreeNode* root, int fa) {
        int u = root->val;
        d[u] = d[fa];
        f[u][0] = fa;
        for (int i = 1; i <= 30; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        if (root->left)dfs(root->left, u);
        if (root->right)dfs(root->right, u);
    }

    int lca(TreeNode* p, TreeNode* q) {
        int u = p->val + 1;
        int v = q->val + 1;
        if (d[u] < d[v])swap(u, v);
        for (int i = 30; i >= 0; i--) {
            if (d[f[u][i]] >= d[v]) {
                u = f[u][i];
            }
        }
        if (u == v) {
            // cout<<10<<endl;
            return u;
        }
        cout << u << " " << v << endl;
        for (int i = 30; i >= 0; i--) {
            //  cout<<u<<" "<<v<<" "<<i<<endl;
            if (f[u][i] != f[v][i]) {
                // cout<<u<<" --"<<v<<endl;
                u = f[u][i];
                v = f[v][i];
                //cout<<u<<" --"<<v<<endl;
            }
        }
        // cout<<u<<" "<<v<<endl;
        return f[u][0];
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        dfs(root, 0);

        int u = lca(p, q);
        //u--;
        TreeNode* ans = new TreeNode(3);
        return ans;
    }
};